class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_sort(head: ListNode) -> ListNode:
    # 递归终止条件：当链表为空或只有一个节点时，直接返回
    if not head or not head.next:
        return head
    
    # 找到链表的中间节点
    mid = get_middle(head)
    left = head
    right = mid.next
    mid.next = None  # 切断链表，分成两部分
    
    # 递归排序左右两部分
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 合并两个已排序的链表
    return merge(left, right)

def get_middle(head: ListNode) -> ListNode:
    slow, fast = head, head
    # fast 指针每次走两步，slow 指针每次走一步，当 fast 到达末尾时，slow 就指向中间节点
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def merge(left: ListNode, right: ListNode) -> ListNode:
    # 创建一个虚拟头节点，便于操作
    dummy = ListNode()
    current = dummy
    
    while left and right:
        if left.val < right.val:
            current.next = left
            left = left.next
        else:
            current.next = right
            right = right.next
        current = current.next
    
    # 如果有剩余的节点，直接连接到结果链表
    if left:
        current.next = left
    elif right:
        current.next = right
    
    return dummy.next

# 测试代码
if __name__ == "__main__":
    # 构建链表 4 -> 2 -> 1 -> 3
    head = ListNode(4)
    head.next = ListNode(2)
    head.next.next = ListNode(1)
    head.next.next.next = ListNode(3)

    # 排序链表
    sorted_head = merge_sort(head)
    
    # 打印排序后的链表
    current = sorted_head
    while current:
        print(current.val, end=" -> " if current.next else "")
        current = current.next
